//给你一个非负整数数组 nums ，你最初位于数组的第一个位置。 
//
// 数组中的每个元素代表你在该位置可以跳跃的最大长度。 
//
// 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 
//
// 假设你总是可以到达数组的最后一个位置。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [2,3,1,1,4]
//输出: 2
//解释: 跳到最后一个位置的最小跳跃数是 2。
//     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
// 
//
// 示例 2: 
//
// 
//输入: nums = [2,3,0,1,4]
//输出: 2
// 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 104 
// 0 <= nums[i] <= 1000 
// 
// Related Topics 贪心 数组 动态规划 
// 👍 1338 👎 0

package com.cute.leetcode.editor.cn;
public class JumpGameIi {
    public static void main(String[] args) {
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 代码随想录的题解看的是后边覆盖的范围，我自己写的是考虑前边的覆盖范围
         * 思路如下：
         *      根据当前nums[i]的值判断能否覆盖的最大范围
         *      如果新的最大范围比当前的范围大，那就更新最大范围
         *      注意：只有当i>preCover的时候，才需要更新步数以及preCover的范围，否则直接在preCover范围内选一个就行了
         */
        public int jump(int[] nums) {
            int len = nums.length;
            if (len == 1) return 0;

            int count = 1;
            int cover = nums[0];//cover记录可以到达的最大下标，即覆盖范围
            int preCover = 0;
            for (int i = 0; i < len; i++) {
                if (nums[i]+i > cover) {//扩大范围时是否需要增加一次跳跃，以及是否更新前边覆盖值
                    if (i > preCover) {//如果i超出了前边的最大范围，均要进行修改
                        // 这里由于i是递增的，preCover如果覆盖不到当前i的话，后边的肯定也覆盖不了
                        // 所以可以直接更新步数
                        count++;
                        preCover = cover;
                    }
                    cover = nums[i]+i;
                }
                if (cover >= len-1) break;
            }
            return count;
        }

        /**
         * 从后向前判断的方法，就是判断会多一些
         */
        public int jump2(int[] nums) {
            int step = 0;
            int left = nums.length - 1;// 反着跳也不是不行，就是会多出很多次尝试
            while (left != 0){
                step++;
                int t = left;
                for (int i = left - 1; i >= 0; i--) if (nums[i] >= left - i) t = i;
                left = t;
            }
            return step;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}